# Linked List (Data Structures) - javatpoint
# https://www.javatpoint.com/ds-linked-list

"""
LinkedList is a data structure that consists of a sequence of nodes, where each node contains data and a reference to the next node in the sequence. It provides an efficient way to store and manipulate elements dynamically.

Properties:
- Each node in a linked list contains two parts: data and a reference (or link) to the next node.
- The first node in the linked list is called the head, and the last node is called the tail. The tail node's reference points to null, indicating the end of the list.
- Unlike arrays, linked lists can grow or shrink dynamically as elements are added or removed.

Operations:

1. Initialization:
   - `LinkedList()`: Creates an empty linked list.

2. Basic Operations:
   - `add_front(data)`: Adds an element to the front of the linked list.
   - `add_end(data)`: Adds an element to the end of the linked list.
   - `insert(data, position)`: Inserts an element at the specified position in the linked list.
   - `remove(data)`: Removes the first occurrence of the specified element from the linked list.
   - `remove_at(position)`: Removes the element at the specified position from the linked list.
   - `search(data)`: Searches for the first occurrence of the specified element in the linked list and returns its position.
   - `get(position)`: Returns the element at the specified position in the linked list.
   - `size()`: Returns the number of elements in the linked list.
   - `is_empty()`: Checks if the linked list is empty.

Example Usage:
```
linked_list = LinkedList()

linked_list.add_front(3)
linked_list.add_end(7)
linked_list.insert(5, 1)
linked_list.remove(3)
print(linked_list.search(7))  # Output: 0
print(linked_list.get(0))  # Output: 7
print(linked_list.size())  # Output: 2
print(linked_list.is_empty())  # Output: False
```

Time and Space Complexity:
- Adding or removing elements at the front or end of a linked list has a time complexity of O(1).
- Inserting or removing elements at a specific position in the linked list has a time complexity of O(n), where n is the number of elements.
- Searching for an element in the linked list has a time complexity of O(n), as it may require traversing the entire list.
- The space complexity of a linked list is O(n), where n is the number of elements, as each element requires a node.
"""

class Node:
    def __init__(self, value=None):
        """
        Initialize a node for use in a linked list.

        Args:
            value: The value to be stored in the node.
        """
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        """
        Initialize an empty linked list.

        Attributes:
            head (Node): The first node in the list.
            tail (Node): The last node in the list.
        """
        self.head = None
        self.tail = None

    def prepend(self, value):
        """
        Insert a new element at the beginning of the list.

        Args:
            value: The value to be stored in the new node.
        """
        new_node = Node(value=value)
        if not self.head:
            self.head = self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def append(self, value):
        """
        Insert a new element at the end of the list.

        Args:
            value: The value to be stored in the new node.
        """
        new_node = Node(value=value)
        if not self.head:
            self.head = self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def find_by_index(self, index):
        """
        Find and return a node at a particular index.

        Args:
            index (int): The index of the node.

        Returns:
            The node at the specified index. If the index is out of range, return None.
        """
        current = self.head
        for i in range(index):
            if current is None:
                return None
            current = current.next
        return current

    def find_by_value(self, value):
        """
        Find and return a node with a particular value.

        Args:
            value: The value to search for.

        Returns:
            The first node that contains the value. If no such node exists, return None.
        """
        current = self.head
        while current is not None:
            if current.value == value:
                return current
            current = current.next
        return None

    def find_min_node(self):
        """
        Find and return the node with the minimum value.

        Returns:
            The node with the smallest value. If the list is empty, return None.
        """
        if self.head is None:
            return None
        min_node = self.head
        current = self.head.next
        while current is not None:
            if current.value < min_node.value:
                min_node = current
            current = current.next
        return min_node

    def __delitem__(self, index):
        """
        Delete the node at the specified index.

        Args:
            index (int): The index of the node to delete.
        
        Raises:
            IndexError: If the index is out of range.
        """
        if self.head is None:
            raise IndexError('LinkedList index out of range')
        
        if index == 0:
            self.head = self.head.next
            if self.head is None or self.head.next is None:
                self.tail = self.head
            return

        prev_node = self.find_by_index(index - 1)
        if prev_node is None or prev_node.next is None:
            raise IndexError('LinkedList index out of range')
        
        prev_node.next = prev_node.next.next
        if prev_node.next is None:
            self.tail = prev_node

    def __len__(self):
        """
        Return the number of elements in the linked list.

        Returns:
            int: The number of elements in the linked list.
        """
        current = self.head
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return count

    def __repr__(self):
        """
        Return a machine-readable string representation of the LinkedList.

        Returns:
            str: A string representation of the LinkedList in the format '<LinkedList: head_value, tail_value, length>'.
        """
        if self.head:
            head_value = self.head.value
        else:
            head_value = None

        if self.tail:
            tail_value = self.tail.value
        else:
            tail_value = None

        length = len(self)

        return f'<LinkedList: head={head_value}, tail={tail_value}, length={length}>'

    def __str__(self):
        """
        Convert the list to a string of node values for easy printing.

        Returns:
            A string representation of the list.
        """
        nodes = []
        current = self.head
        while current:
            nodes.append(f'Node(value={current.value}, next={current.next.value if current.next else "None"})')
            current = current.next
        return " -> ".join(nodes)


if __name__ == "__main__":
    linked_list = LinkedList()

    linked_list.append(5)
    linked_list.append(10)
    linked_list.append(15)
    linked_list.prepend(1)

    print(f"LinkedList: {linked_list}")  # LinkedList: Node(value=1, next=5) -> Node(value=5, next=10) -> Node(value=10, next=15) -> Node(value=15, next=None)

    node = linked_list.find_by_index(2)
    if node:
        print(f"Value at index 2: {node.value}")  # Value at index 2: 10
    else:
        print("Index out of range.")

    node = linked_list.find_by_value(10)
    if node:
        print(f"Found node with value 10")  # Found node with value 10
    else:
        print("Value not found in linked list.")

    min_node = linked_list.find_min_node()
    if min_node:
        print(f"Node with minimum value: {min_node.value}")  # Node with minimum value: 1
    else:
        print("LinkedList is empty.")

    del linked_list[1]
    print(f"LinkedList after deleting value at index 1: {linked_list}")  # LinkedList after deleting value at index 1: Node(value=1, next=10) -> Node(value=10, next=15)

    print(repr(linked_list))  # <LinkedList: head=1, tail=15, length=2>
